1. Field of the Invention
The present invention relates to a contents addressable memory (CAM), and more particularly to a contents addressable memory with accelerated exchanging within a cell array of entry data that has been stored in memory cells.
2. Description of the Related Art
A contents addressable memory (hereinafter simply referred to as CAM) is also called associative memory and outputs addresses in which input data is stored for that input data. FIG. 1 explains the differences between an ordinary memory and CAM. In an ordinary memory, data stored in an address within the memory is output when that address is input. In contrast, with CAM, the address in which data is stored is output when data is entered.
With the popularization of the Internet in recent years, demand for such CAM is increasing. That is, when ordinary CAM is used to enable a network server to refer to an IP address embedded in the transfer data packet and to detect the transfer destination data, the IP address is input into CAM as data, the corresponding address is read, and the transfer destination data is detected based on the address thus read.
CAM includes a memory cell array in the same way as an ordinary memory. In addition, just as with an ordinary memory, by inputing an address, a desired data can be written to or read from the memory cell array. Furthermore, CAM has a comparison means for comparing entered data, known as entry keys, and stored data, known as entry data that is stored in a memory cell array. Any memory cell address in which both match is output as a matching address.
One specific function of CAM is an exchanging of entry data within a memory cell array. When priority must be given to entry data strings, the entry data strings are stored within the memory cell array in accordance with their priority. That order of priority is reviewed at prescribed intervals. Accordingly, after the order of priority is reviewed, the entry data must be re-arranged within the memory cell array using the new order of priority. Alternatively, the new entry data must be written in a prescribed address position within the entry data string in the memory cell array. Here too, entry data stored in or below the newly written address must be transferred to a lower or higher address.
Transfer of entry data is required to enable the re-arrangement or writing of entry data as described above. Such transfer is realized by multiple repetitions of operations in which simply stored entry data is read and written to a new address position. The repetition of these read and write operations of CAM is not desirable since it dramatically reduces the performance of the system in which CAM is mounted.
Thus, an object of the present invention is to provide a CAM that can transfer stored data within a cell array at high speed.
Another object of the present invention is to provide a CAM that can transfer stored data within a cell array without reading to or writing from external equipment the data.
To achieve the above objects, one aspect of the present invention is a contents addressable memory, comprising: memory cells arranged in a matrix at positions where word lines extending along a row cross bit lines extending along a column; search buses extending along the column and match lines extending along the row; and a comparison circuit provided in each memory cell and which compares data in the search bus and data stored in memory cell and outputs comparison result to the match line; wherein transfer units having a first transfer gate, a transfer cell for temporarily storing data from said memory cell, and a second transfer gate are provided between a pair of memory cells arranged along the column; and data from one of pair of memory cells is stored in the transfer cell via the first or second transfer gate, then that data thus stored in the transfer cell is stored in other of pair of memory cells via the second or first transfer gate.
In the above invention, transfer units are provided between a pair of memory cells arranged along the column. For example, the first transfer gate is opened and data in one of the pair of memory cells is transferred to the transfer cell and temporarily stored there. The first transfer gate is then closed, the second transfer gate is opened, and the data temporarily stored in the transfer cell is transferred to the other memory cell in the pair. This transfer operation ensures that the stored data can be transfered within a cell array without requiring it to be read to or written from external equipment.
In a more preferable embodiment of the present invention, by arranging the above transfer unit between memory cells that are adjacent along the column, data from a plurality of memory cells can be transferred to each corresponding adjacent memory cells in the same column. Accordingly, there is no need for repeated operations involving the reading of data in memory cells in one row and writing of it to memory cells in another row.
In a more preferable embodiment of the present invention, the above transfer cell has a capacitor in which data is stored, and the memory cell has a latch circuit that cross-connects a pair of inverters. Furthermore, when data is transferred from the transfer cell, the memory cell latch circuit is temporarily made neutral and then the transfer data is latched. In this embodiment, since the transfer cell comprises capacitors of a passive element and has no drive capability, so when data is to be transferred to a memory cell configured with a latch circuit, a short-circuit is produced between the nodes of this latch circuit, so that the circuit is placed in a neutral status, and then transfer data is latched. This means that the transfer data in the capacitor can be latched by the memory cell latch circuit even if there is no drive element in the transfer cell.
In another preferable embodiment of the present invention, the above transfer cell has a latch circuit that cross-connects a pair of inverters. Furthermore, when data is to be transferred from the above transfer cell, the latch operation of the memory cell latch circuit is temporarily released and the memory cell is driven from the latch circuit in the transfer cell. Thereafter, the transfer data is latched by the memory cell. When the second transfer gate is opened and data is transferred from the transfer cell, temporary release of the latch operation in the memory cell latch circuit enables accurate transfer of data even when the drive capability of the latch circuit in the transfer cell is low.
To achieve the above objects, another aspect of the present invention is a contents addressable memory that compares stored data and input data, and outputs address information in which matching data is stored, comprising: memory cells arranged in a matrix at positions where word lines extending along a row cross bit lines extending along a column; search buss extending along the column and match lines extending along the row; a comparison circuit provided in each memory cell and which compares data in the search bus and data stored in memory cell and outputs comparison result to the match line; and transfer units each provided between a pair of memory cells arranged along the column and each comprising a first transfer gate, a transfer cell for temporarily storing data from the memory cell, and a second transfer gate; wherein data from one of pair of memory cells is stored in the transfer cell via the first or second transfer gate, then the data thus stored in the transfer cell is stored in other of pair of memory cells via the second or first transfer gate.